/**
 * Created by sunchenglin on 2017/7/17.
 *基数排序
 //    拓扑排序
 //    K路归并排序

 */
public class Solution {
    public static void change(int i, int j, int[] array){
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public static int getmax(int[] array,int d){
        int max=0;
        int temp;
        for(int i=0;i<array.length;i++){
            temp = Integer.parseInt(String.valueOf(String.valueOf(array[i]).toCharArray()[d]));
            if(temp >max){
                max =temp;
            }
        }
        return max;
    }
    //数组A 0,n存放输入数组

//数组B 0,n, 存放排序后的数组

//数组C 0,k，辅助数组，存放i的个数。 计数排序的稳定性呢？

    public static int[] countingSort(int[] array, int d,int maxd){
        int[] b = new int[array.length];
        int[] c = new int[getmax(array,d)+1];
        int temp;
        for(int i=0; i<c.length; i++){
            c[i] = 0;
        }
        for(int i=0; i<array.length; i++){
            c[Integer.parseInt(String.valueOf(String.valueOf(array[i]).toCharArray()[d]))]++;
        }
        for(int i=1; i<c.length;i++){
            c[i] = c[i-1]+c[i];
        }
        for(int i=array.length-1; i>=0; i--){
            temp = Integer.parseInt(String.valueOf(String.valueOf(array[i]).toCharArray()[d]));
            b[c[temp]-1] = array[i];
            c[temp]--;
        }
        return b;
    }


//数组A 所有数据为d个位数。

    public static void baseSort(int[] array){
        int d = 0;
        d = String.valueOf(array[0]).toCharArray().length;
        for(int i=0; i<array.length; i++){
            if(d != String.valueOf(array[i]).toCharArray().length) return;
        }
        for(int i=d-1; i>=0; i--){
            array = countingSort(array,i,d);
        }
        System.out.println("he");
    }

    public static void main(String args[]){
        int[] a={1234,2123,2124,2342,2128,2346,4352};
        baseSort(a);
        System.out.println("haha");
    }
}
